class Solution:
    def largestDivisibleSubset(self, nums: list) -> list:
        length = len(nums)
        if length < 2:
            return nums
        nums.sort()
        dp = [1] * length
        pre = [-1] * length
        for i in range(1, length):
            for j in range(0, i):
                if nums[i] % nums[j] == 0 and dp[j] + 1 > dp[i]:
                    dp[i] = dp[j] + 1
                    pre[i] = j
        res = []
        max_index = dp.index(max(dp))
        while max_index >= 0:
            res.append(nums[max_index])
            max_index = pre[max_index]
        return res


a = Solution()
print(a.largestDivisibleSubset([1, 2, 3]))
print(a.largestDivisibleSubset([1,2,4,8]))
